package mashibing.basic.class01;

import java.util.Arrays;

/**
 * 有序数组二分法查找 + 对数器
 */
// 重点：
// int 内存溢出 2^31 ~ 2^31-1 （2147483648 ~ 2147483647）21亿
//	N / 2 == N >> 1 有符号右移：常数项能优化就优化
public class Code04_BSExist {
	// 二分法查找：有序数组中查找数据是否存在
	public static boolean exist(int[] sortedArr, int num) {
		if (sortedArr == null || sortedArr.length == 0) {
			return false;
		}
		int L = 0;// 左侧下标
		int R = sortedArr.length - 1;// 右侧下标
		int mid = 0;// 终点
		// L..R
		while (L < R) { // L..R 至少两个数的时候
			// (L + R)/2 不安全，int 内存溢出
			// mid = L + (R - L)/2
			mid = L + ((R - L) >> 1); // N / 2 == N >> 1 有符号右移：常数项能优化就优化
			if (sortedArr[mid] == num) {
				return true;
			} else if (sortedArr[mid] > num) {
				// L  mid  R
				// L R
				R = mid - 1;
			} else {
				// L  mid  R
				//       L R
				L = mid + 1;
			}
		}
		// 可以用L <= R，两种方法，另外扣边界
		return sortedArr[L] == num;// L = r的时候；需要自己扣边界
	}
	
	// for test ：for循环查找
	public static boolean test(int[] sortedArr, int num) {
		for(int cur : sortedArr) {
			if(cur == num) {
				return true;
			}
		}
		return false;
	}
	
	
	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		// Math.random() -> [0,1) 所有小数等概率返回一个
		// Math.random() * N -> [0,N) 所有小数等概率返回一个
		// (int)Math.random() -> [0,N -1] 所有整数等概率返回一个
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());// 有正有负有0，因为两个数可能不一样
		}
		return arr;
	}
	
	public static void main(String[] args) {
		int testTime = 500000;
		int maxSize = 10;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr = generateRandomArray(maxSize, maxValue);
			Arrays.sort(arr);
			int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
			if (test(arr, value) != exist(arr, value)) {// 这个随机数要么都存在要么都不存在
				succeed = false;
				break;
			}
		}
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");
	}

}
